Signature de Lamport
En cryptologie, le schéma de signature de Lamport[a],[1] est un mécanisme à usage unique[b] permettant de signer numériquement un document[2]. Il a été introduit en 1979 par l'informaticien américain Leslie Lamport[3]. La construction des signatures de Lamport repose uniquement sur les fonctions à sens unique, une approche qui a inspiré plusieurs constructions cryptographiques et qui s'avère être un candidat post-quantique[4].
Les signatures de Lamport souffrent de nombreux désavantages techniques, en particulier leur usage unique, la taille des clés et des signatures[5], qui ont motivé la création d'algorithmes plus efficaces (par Merkle et d'autres).
Description
[modifier | modifier le code]Le schéma de signature de Lamport est composé de trois algorithmes : génération de clés, signature et vérification.
Génération de clés
[modifier | modifier le code]L'algorithme de génération de clés prend en entrées un paramètre de sécurité et une taille de messages , puis détermine deux entiers , et une fonction à sens unique . L'algorithme de génération de clés tire ensuite éléments uniformément au hasard pour et .
L'algorithme retourne la clé privée , la clé publique et les paramètres publics .
Signature
[modifier | modifier le code]L'algorithme de signature prend en entrées les paramètres publics, la clé privée, et un message à signer. La signature correspondante est .
Vérification
[modifier | modifier le code]L'algorithme de vérification prend en entrées les paramètres publics, la clé publique, un message et une signature . S'il existe un indice tel que alors l'algorithme retourne une erreur. Sinon, il renvoie un succès.
Sécurité
[modifier | modifier le code]La sécurité du schéma de signature de Lamport face aux contrefaçons existentielles se ramène immédiatement (et dans le modèle standard) à la difficulté de calculer une préimage pour [6],[c]. Cependant, le schéma ne peut être utilisé que pour signer un seul message. En effet, la signature révèle par construction une partie (50%) de la clé privée.
Un calculateur quantique facilite la recherche d'une préimage (au moyen de l'algorithme de Grover), divisant par deux le niveau de sécurité par rapport à un adversaire classique. Ce phénomène est aisément compensé en doublant les paramètres de la fonction ; pour cette raison, le schéma de Lamport est considéré comme un candidat post-quantique[4],[7].
Notes et références
[modifier | modifier le code]Notes
[modifier | modifier le code]- Parfois appelé « schéma de signature de Lamport-Diffie », puisqu'on peut retracer l'idée à (Diffie et Hellman 1976, p. 650), mais la construction en entier et l'analyse de sécurité apparaissent pour la première fois dans (Lamport 1979).
- On parle dans ce contexte de « signature à usage unique », ou de « signature jetable » (OTS, pour l'anglais one time signature), en analogie au masque jetable pour le chiffrement.
- Pour les implémentations, une fonction de hachage cryptographique pourra jouer ce rôle.
Références
[modifier | modifier le code]- (en) W. Diffie et M. Hellman, « New directions in cryptography », IEEE Transactions on Information Theory, vol. 22, no 6, , p. 644–654 (ISSN 0018-9448, DOI 10.1109/tit.1976.1055638, lire en ligne, consulté le )
- (en) Leslie Lamport, Constructing digital signatures from a one-way function, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Oct. 1979.
- (en) Tanja Lange, « Hash-Based Signatures », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_413, lire en ligne), p. 540–542
- Guillot, Philippe., La cryptologie : l'art des codes secrets, EDP Sciences, , 196 p. (ISBN 978-2-7598-0995-0 et 2759809951, OCLC 854569776, lire en ligne), p. 143
- (en) Anna Lysyanskaya, « Lecture 17: Digital Signature Schemes »,
- (en) Daniel J. Bernstein, « Post-Quantum Cryptography », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_386, lire en ligne), p. 949–950